package leetcode.code0730;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	int mod = (int) 1e9 + 7;

	public int countPalindromicSubsequences(String s) {
		char[] cs = s.toCharArray();
		int len = cs.length;
		Integer[][] dp = new Integer[len][len];
		return this.count(cs, 0, len - 1, dp);
	}

	private int count(char[] cs, int l, int r, Integer[][] dp) {
		if (l == r) {
			return 1;
		}
		if (dp[l][r] != null) {
			return dp[l][r];
		}
		long ans1 = this.count(cs, l, r, 'a', dp);
		long ans2 = this.count(cs, l, r, 'b', dp);
		long ans3 = this.count(cs, l, r, 'c', dp);
		long ans4 = this.count(cs, l, r, 'd', dp);
		dp[l][r] = (int) ((ans1 + ans2 + ans3 + ans4) % mod);
		return dp[l][r];
	}

	private long count(char[] cs, int l, int r, char c, Integer[][] dp) {
		if (l > r) {
			return 0;
		}
		if (l == r) {
			return cs[l] == c ? 1 : 0;
		}
		char L = cs[l];
		char R = cs[r];
		long ans = 0;
		if (L == c && R == c) {
			ans = 2 + this.count(cs, l + 1, r - 1, dp);
		} else if (L == c && R != c) {
			ans = this.count(cs, l, r - 1, c, dp);
		} else if (L != c && R == c) {
			ans = this.count(cs, l + 1, r, c, dp);
		} else if (L != c && R != c) {
			ans = this.count(cs, l + 1, r - 1, c, dp);
		}
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(6, this.countPalindromicSubsequences("bccb"));
		H.compare(104860361, this.countPalindromicSubsequences("abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
